#define  _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>

using namespace std;

//重做最长湍流子数组
//昨天做了摆动序列这道题给了我很大启发，发现和最长湍流子数组几乎完全一样，区别只在于子数组和子序列这个地方
//而先做子数组这个问题的时候虽然过了但是做得很糙，代码写的很烂，借助摆动序列的思路重新做一下这个题
//依旧是对多状态问题的思考，不仅代码变得更加简洁，思路也更清晰
//之前将等于的这种情况单独拎出来都不知道怎么过的，这样最后的状态分别考虑了<  >  = 这三种情况
class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int n = arr.size();
        //创建dp表
        vector<int> f(n, 1), g(n, 1);

        int ret = 1;
        //填表
        for (int i = 1; i < n; i++)
        {
            if (arr[i - 1] < arr[i]) f[i] = g[i - 1] + 1;
            else if (arr[i - 1] > arr[i]) g[i] = f[i - 1] + 1;
            ret = max(ret, max(f[i], g[i]));
        }
        //返回值
        return ret;
    }
};

//最长递增子序列的个数
//自己的思路但是没过
class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();

        //创建dp表
        vector<vector<int>> dp(2, vector<int>(n));
        //初始化
        for (int i = 0; i < n; i++) dp[0][i] = 1;

        int ans = 1;

        //填表
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (nums[j] < nums[i]) dp[0][i] = max(dp[0][j] + 1, dp[0][i]);
            }
            for (int j = 0; j < i; j++)
            {
                if (nums[j] < nums[i] && dp[0][i] == (dp[0][j] + 1)) dp[1][i]++;
            }
            if (dp[0][i] == 1) dp[1][i]++;
            ans = max(ans, dp[0][i]);
        }
        //返回值
        int ret = 0;
        for (int i = 0; i < n; i++) if (ans == dp[0][i])  ret += dp[1][i];

        return ret;




    }
};

int main()
{
	return 0;
}